package leetcode.editor.cn;//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
//
//
// 示例 1：
//
//
//输入：l1 = [1,2,4], l2 = [1,3,4]
//输出：[1,1,2,3,4,4]
//
//
// 示例 2：
//
//
//输入：l1 = [], l2 = []
//输出：[]
//
//
// 示例 3：
//
//
//输入：l1 = [], l2 = [0]
//输出：[0]
//
//
//
//
// 提示：
//
//
// 两个链表的节点数目范围是 [0, 50]
// -100 <= Node.val <= 100
// l1 和 l2 均按 非递减顺序 排列
//
// Related Topics 递归 链表
// 👍 2110 👎 0


//leetcode submit region begin(Prohibit modification and deletion)


import leetcode.editor.cn.entity.BaseClass;
import leetcode.editor.cn.entity.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution21 {


    public static void main(String[] args) {


        ListNode node1 = new ListNode(1);
        ListNode node12 = new ListNode(2);
        ListNode node13 = new ListNode(4);

        ListNode node2 = new ListNode(1);
        ListNode node21 = new ListNode(3);
        ListNode node22 = new ListNode(4);


        node12.next = node13;
        node1.next = node12;

        node21.next = node22;
        node2.next = node21;
        ListNode node = mergeTwoLists(node1,node2);
    }



    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 虚拟头节点
        ListNode dummy = new ListNode(-1),p =dummy;
        ListNode p1 = list1,p2 = list2;
        // 比较 p1和p2两个指针，将小的节点连接到p指针
        while (p1 != null && p2 != null){

           if (p1.val>p2.val){

               p.next = p2;
               p2 = p2.next;

           }else {
               p.next = p1;
               p1 = p1.next;
           }
           // p 指针不断前进
           p = p.next;

        }
        if (p1 != null){
            p.next = p1;
        }
        if (p2 != null){
            p.next = p2;
        }

        return dummy.next;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
/**

 单链表有很多巧妙的操作,这些解法都用到了双指针技巧，所以说对于单链表相关的题目，双指针的运用是非常广泛的

 这个算法的逻辑类似于「拉拉链」，l1, l2 类似于拉链两侧的锯齿，指针 p 就好像拉链的拉索，将两个有序链表合并。

 代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。你可以试试，
 如果不使用 dummy 虚拟节点，代码会复杂很多，而有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。


 **/
